/**
 * 
 */
package problem.array;

/**
 * 树状树组，便于连续数组项前N项的求和和更新
 * http://fqq11679.blog.hexun.com/21722866_d.html
 * @author Jun
 *
 */
public class TreeArray {

	private int[] array;
	
	//treeArr[i]表示array[i-2^k+1]到array[i]的和
	public int[] treeArr;
	
	private int _length = 0;
	
	public TreeArray(int[] newarray){
		
		array = newarray.clone(); 
		_length = array.length;
		init();
	}
	
	private void init(){
		
		treeArr = new int[_length];
		int lowbit = 0;
		
		for(int i=1; i< _length; i++){
			
			lowbit = Lowbit(i);
			
			//计算treeArr[i]
			treeArr[i] = array[i];
			lowbit >>= 1;		
			while(lowbit>0){		
				
				treeArr[i] += treeArr[i-lowbit];
				lowbit >>= 1;				
			}
		}
	}
	
	
	/**
	 * 计算父结点下标
	 * @param i
	 * @return
	 */
	private int ParentIndex(int i){		
		
		return i + Lowbit(i);		
		
	}
	
	/**
	 * 计算前棵子树的下标
	 * @param i
	 * @return
	 */
	private int PreIndex(int i){		
		
		return i - Lowbit(i);		
		
	}
	
	
	/**
	 * 计算最小幂2(K)
	 * @param i
	 * @return
	 */
	public int Lowbit(int i){
		
		return i&(i^(i-1));
		//或使用机器补码 return i&(-i);
	}
	
	/**
	 * 如果要把a[n]增加m
	 * @param pos
	 * @param num
	 */
	public void plus(int pos , int num){
		
		array[pos] += num;
		while(pos<=_length){
			
			treeArr[pos] += num;
			pos += Lowbit(pos);
		}
		
	}
	
	/**
	 * 如果要统计a[1]到a[n]之间的和
	 * @param i
	 * @return
	 */
	public int Sum(int i){
		
		int sum = 0;
		while(i>0){
			sum += treeArr[i];
			i -= Lowbit(i);	
		}
		return sum;
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] srcArr = {0,1,1,1,1,1,1,1,1};		
		TreeArray ins = new TreeArray(srcArr);
		
		
		
	}

}
